home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / tex / gestalt.zip / SIMIL_C.ASM < prev    next >
Assembly Source File  |  1988-12-06  |  13KB  |  336 lines
  1. ;From the article "Pattern Matching - The Gestalt Approach"
  2. ;by John W. Ratcliff and David E. Metzener
  3. ;Dr. Dobbs Journal, July 1988
  4. ;Typed in 6 Dec 88, and very slightly tweaked (see the 'TH' comments).
  5. ; (I don't have a C compiler, so couldn't test this particular code.
  6. ;  See other files for assembly language program and Turbo Pascal
  7. ;  compatible procedures.)
  8. ;
  9. ; David Kirschbaum
  10. ; Toad Hall
  11. ; kirsch@braggvax.ARPA
  12.  
  13.  
  14. TITLE    SIMIL.ASM written by John W. Ratcliff and David E. Metzener
  15.  
  16. ; November 10, 1987
  17. ; Uses the Ratcliff/Obershelp pattern recognition algorithm.
  18. ; This program provides a new function to C on an 8086 based machine.
  19. ; The function SIMIL returns a percentage value corresponding to how
  20. ; alike any two strings are.  Be certain to upper case the two strings
  21. ; passed if you are not concerned about case sensitivity.
  22. ; NOTE:  This routine is for SMALL model only.  As an exercise for
  23. ; the student, feel free to convert it to LARGE.
  24.  
  25. _TEXT    SEGMENT    BYTE PUBLIC 'CODE'
  26. _TEXT    ENDS
  27. CONST    SEGMENT    WORD PUBLIC 'CONST'
  28. CONST    ENDS
  29. _BSS    SEGMENT    WORD PUBLIC 'BSS'
  30. _BSS    ENDS
  31. _DATA    SEGMENT    WORD PUBLIC 'DATA'
  32. _DATA    ENDS
  33. DGROUP    GROUP    CONST,    _BSS,    _DATA
  34.     ASSUME    CS:_TEXT, DS:DGROUP, SS:DGROUP, ES:DGROUP
  35.  
  36. _DATA    SEGMENT
  37.  
  38. ststr1L    dw    25 dup(?)        ;contains lefts for string 1
  39. ststr1R    dw    25 dup(?)        ;contains rights for string 1
  40. ststr2L    dw    25 dup(?)        ;contains lefts for string 2
  41. ststr2R    dw    25 dup(?)        ;contains rights for string 2
  42. stcknum    dw    ?            ;number of elements on the stack
  43. score    dw    ?            ;the # of chars in common times 2
  44. total    dw    ?            ;total # of chars in string 1 and 2
  45. cL1    dw    ?            ;left of string 1 found in common
  46. cR1    dw    ?            ;right of string 1 found in common
  47. cL2    dw    ?            ;left of string 2 found in common
  48. cR2    dw    ?            ;right of string 2 found in common
  49. s2ed    dw    ?            ;the end of string 2 used in compare
  50.  
  51. _DATA    ENDS
  52.  
  53.     public    _simil
  54.  
  55. _TEXT    SEGMENT
  56.  
  57. _simil    proc    near
  58. ; This routine expects pointers passed in two character strings, null
  59. ; terminated, that you wish compared.  It returns a percentage value
  60. ; from 0 to 100% corresponding to how alike the two strings are.
  61. ;             +4        +6
  62. ; usage:  simil(char *str1,char *str2)
  63. ; The similarity routine is composed of three major components
  64. ; pushst    --- pushes a string section to be compared on the stack
  65. ; popst        --- pops a string section to be examined off of the stack
  66. ; compare    --- finds the largest group of characters in common between
  67. ;            any two string sections
  68. ; The similarity routine begins by computing the total length of both
  69. ; strings passed and placing that value in TOTAL.  It then takes
  70. ; the beginning and ending of both strings passed and pushes them on
  71. ; the stack.  It then falls into the main line code.
  72. ; The original two strings are immediately popped off of the stack and
  73. ; are passed to the compare routine.  The compare routine will find the
  74. ; largest group of characters in common between the two strings.
  75. ; The number of characters in common is multiplied times two and added
  76. ; to the total score.  If there were no characters in common, then there
  77. ; is nothing to push onto the stack.  If there are exactly one character
  78. ; to the left in both strings, then we needn't push it on the stack.
  79. ; (We already know they aren't equal from the previous call to compare.)
  80. ; Otherwise the characters to the left are pushed onto the stack.  These
  81. ; same rules apply to characters to the right of the substring found in
  82. ; common.  This process of pulling substrings off of the stack, comparing
  83. ; them, and pushing remaining sections on the stack is continued until
  84. ; the stack is empty.  On return the total score is divided by the
  85. ; number of characters in both strings.  This is multiplied times 100 to
  86. ; yield a percentage.  This percentage similarity is returned to the
  87. ; calling procedure.
  88.  
  89.     push    bp        ;save BP reg.
  90.     mov    bp,sp        ;save SP reg in BP for use in program
  91.     push    ES        ;save the ES seg register
  92.     mov    ax,DS        ;copy DS segment reg to ES
  93.     mov    ES,ax
  94.     xor    ax,ax        ;zero out AX for clearing of SCORE var
  95.     mov    score,ax    ;zero out SCORE
  96.     mov    stcknum,ax    ;initialize number of stack entries to 0
  97.     mov    si,[bp+4]    ;move beginning pointer of string 1 to SI
  98.     mov    di,[bp+6]    ;move beginning pointer of string 2 to SI
  99.     cmp    [si],al        ;is it a null string?
  100.     je    StrErr        ;can't process null strings
  101.     cmp    [di],al        ;is it a null string?
  102.     jne    DoCmp        ;Neither is a null string, so process them
  103. StrErr:    jmp    Donit        ;exit routine
  104.  
  105. DoCmp:    push    di        ;save DI because of SCAS opcode
  106.     push    si        ;save SI because of SCAS opcode
  107.     xor    al,al        ;clear out AL to search for end of string
  108.     cld            ;set direction flag forward
  109.     mov    cx,-1        ;make sure we repeat the correct # of times
  110.  
  111.     repnz    scasb        ;scan for string delimiter in string 2
  112.     dec    di        ;point DI to '$00' byte of string 2
  113.     dec    di        ;point DI to last char of string 2
  114.     mov    bp,di        ;move DI to BP where it is supposed to be
  115.  
  116.     pop    di        ;restore SI into DI for SCAS (string 1)
  117.     repnz    scasb        ;scan for string delimiter in string 1
  118.  
  119.     not    cx        ;do one's complement for correct length of st
  120.     sub    cx,2        ;subtract the two zero bytes at the end of st
  121.     mov    total,cx    ;store string 2's length
  122.  
  123.     dec    di        ;point DI to '$00' byte of string 1
  124.     dec    di        ;point DI to last char of string 1
  125.     mov    bx,di        ;move DI to BX where it is supposed to be
  126.  
  127.     pop    di        ;restore DI to what it should be
  128.     call    PushSt        ;push values for the first call to SIMILIARITY
  129.  
  130. Main:    cmp    stcknum,0    ;is there anything on the stack?
  131.     je    Done        ;no, then all done!
  132.  
  133.     call    PopSt        ;get regs set up for a compare call
  134.     call    Compare        ;do compare for this substring set
  135. ;TH    cmp    dx,0        ;if nothing in common then nothing to push
  136. ;TH    je    Main        ;try another set
  137.     or    dx,dx        ;if nothing in common then nothing to push TH
  138.     jz    Main        ;try another set            TH
  139.  
  140.     shl    dx,1        ;*2 for add to score
  141.     add    score,dx    ;add into score
  142.     mov    bp,stcknum    ;get number of entry I want to look at
  143.     shl    bp,1        ;get AX ready to access string stacks
  144.     mov    si,[ststr1L+bp]    ;move L1 into SI or L1
  145.     mov    bx,cL1        ;move CL1 into BX or R1
  146.     mov    di,[ststr2L+bp]    ;move L2 into DI or L2
  147.     mov    cx,cL2        ;move CL2 into CX temporarily
  148.     mov    ax,[ststr1R+bp]    ;get old R1 off of stack
  149.     mov    cL1,ax        ;place in CL1 temporarily
  150.     mov    ax,[ststr2R+bp]    ;get old R2 off of stack
  151.     mov    cL2,ax        ;save in CL2 temporarily
  152.     mov    bp,cx        ;place CL2 into BP
  153.  
  154.     cmp    bx,si        ;compare CL1 to L1
  155.     je    Chrght        ;if zero, then nothing on left side string 1
  156.  
  157.     cmp    bp,di        ;compare CL2 to L2
  158.     je    Chrght        ;if zero, then nothing on left side string 2
  159.  
  160.     dec    bx        ;point to last part of left side string 1
  161.     dec    bp        ;point to last part of left side string 2
  162.     cmp    bx,si        ;only one char to examine?
  163.     jne    PushIt        ;no->we need to examine this
  164.     cmp    bp,di        ;only one char in both?
  165.     je    Chrght        ;nothing to look at if both only contain 1 char
  166.  
  167. PushIt:    call    PushSt        ;push left side on stack
  168. Chrght:    mov    si,cR1        ;move CR1 into SI or L1
  169.     mov    bx,cL1        ;move R1 into BX or R1
  170.     mov    di,cR2        ;move CR2 into DI or L2
  171.     mov    bp,cL2        ;move R2 into BP or R2
  172.  
  173.     cmp    si,bx        ;compare CR1 to R1
  174.     je    Main        ;If zero, then nothing on right side string 1
  175.     cmp    di,bp        ;compare CR2 to R2
  176.     je    Main        ;if zero, then nothing on right side string 2
  177.  
  178.     inc    si        ;point to last part of right side string 1
  179.     inc    di        ;point to last part of right side string 2
  180.     cmp    bx,si        ;only one char to examine?
  181.     jne    Push2        ;no-> examine it
  182.     cmp    bp,di        ;only 1 char to examine in both?
  183.     je    Main        ;yes-> get next string off of stack
  184.  
  185. Push2:    call    PushSt        ;push right side on stack
  186.     jmp    short Main    ;do next level of compares
  187.  
  188. Done:    mov    ax,score    ;get score into AX for MUL
  189.     mov    cx,100        ;get 100 into CX for MUL
  190.     mul    cx        ;multiply by 100
  191.     mov    cx,total    ;get total chars for divide
  192.     div    cx        ;divide by total
  193. Donit:    pop    es        ;restore ES to entry value
  194.     pop    bp        ;restore BP back to entry value
  195.     ret            ;leave with AX holding % similarity
  196. _simil    endp
  197.  
  198. Compare    proc    near
  199.  
  200. ; The compare routine locates the largest group of characters between string 1
  201. ; and string 2.  This routine assumes that the direction flag is clear.
  202. ; Pass to this routine:
  203. ;    BX    = R1 (right side of string 1)
  204. ;    DS:SI    = L1 (left side of string 1)
  205. ;    ES